1. Field of the Invention
The present invention generally relates to the turbo encoding technique that effectively copes with a burst error. More particularly, the present invention is concerned with an interleaving method, an interleaving apparatus, a turbo encoding method, and a turbo encoder in which pruning is not performed at all or only a small number of bits is pruned away, so that computational complexity can be reduced.
The present invention can be applied to fields required to improve reliability of communications using error correction codes, such as digital transmissions and digital recording. The present invention is particularly effective in fields which require flexibility of communications such as multimedia.
2. Description of the Related Art
Recently, a turbo encoder has been proposed which utilizes a code having high capability in error correction. Such a turbo encoder is made up of a plurality of encoders, which are coupled together via an interleaver (which is means for performing interleaving processing) in order to reduce the correlation between redundant sequences associated with the respective encoders. The interleaver is a key element which determines the performance of turbo encoding.
FIGS. 1A and 1B show an example of the turbo encoder. As shown in FIG. 1A, the turbo encoder includes recursive systematic convolutional encoders 12 (RSC1) and 13 (RSC2), and an interleaver 11. As shown in FIG. 1B, each of the encoders 12 and 13 is made up of adders 14 and 15 and delay elements (D) 16 and 17 connected as shown therein. The turbo encoder receives an input data sequence d (K bits) and outputs encoded data sequences X1-X3. In order to reduce the correlation between the redundant bits X1 and X2, the interleaver 11 is provided at the input side of the encoder (RSC2) 13. As shown in FIG. 1C, a turbo decoder is made up to two decoders 1 and 2, two interleavers 3 and 4, and a deinterleaver 5.
In digital systems, permutation in interleaving is performed on a given unit basis of bit or symbol. The permutation is implemented by using a buffer or a pattern for permutation. When the buffer is used, data is written therein and is then read therefrom in a different sequence. When the pattern for permutation is used, data is permuted by referring to the pattern, which describes information concerning a permutation based on interleaving. The pattern described will be referred to as an interleave pattern.
A description will now be given of bit-based permutation processing using the interleave pattern.
FIG. 2 shows interleaving of a 16-bit sequence. In FIG. 2, a 16-bit sequence 67 is interleaved on the bit unit basis by referring to an interleave pattern table 68, which defines a sequence of interleaving. More particularly, the zeroth to 15th bits of the sequence 67 is written into a two-dimensional buffer by the interleave pattern table 68, and is then read therefrom in the order of 0, 8, 4, 12, . . . , as indicated by an arrow in FIG. 2. Thus, a bit sequence after interleaving is obtained as shown in FIG. 2.
The interleaver involved in interleaving is required to have the following three capabilities of:
(1) handling a variety of frame lengths (for example, thousands to ten thousands);
(2) producing the interleaved sequence with a small number of parameters; and
(3) reducing computational complexity in creating the interleave pattern.
As to the first capability, if the parameters are merely prepared for all of the different frame lengths, a huge number of parameters will be prepared, and a huge memory capacity will be required to store the parameters. Thus, the above is impractical. There is another disadvantage that it takes a long time to compute respective optimal parameters for each of the different frame lengths.
The above problems may be solved by designing interleavers with a small number of parameters. This is related to the second capability. Interleavers equal in number to a power of 2 are prepared and pruning of data is performed. However, pruning of data requires an increased number of parameters for optimization, and the interleavers may not have good performance with respect to all of the frame lengths. That is, the interleavers have good performance for some frame lengths but do not operate well for other frame lengths.
Reduction in the amount of data to be pruned away is also related to the third capability. In this regard, the present inventors have proposed an improvement in pruning and performance (International Application No. PCT/JP98/05027). However, even the proposed improvement has high computational complexity in producing the interleave patterns.
It is a general object of the present invention to provide an improved interleaving technique having the above-mentioned three capabilities.
A more specific object of the present invention is to provide an interleaving method, an interleaving apparatus, a turbo encoding method and a turbo encoder capable of efficiently achieving randomization of input sequences of a variety of frame lengths with reduced computational complexity.
The above objects of the present invention are achieved by 1. An interleaving method comprising the steps of: receiving a data sequence having a plurality of blocks each having a length based on a prime number P; generating sequence permutation data by performing a given operation on elements of a Galois field of a characteristic P and permuting results of the given operation, so that sequence permutation data are generated; and permuting a sequence of data of the data sequence in accordance with the sequence permutation data.
The above objects of the present invention are also achieved by an interleaving method comprising the steps of: (a) generating or recording a prime number P; (b) dividing an input sequence into N blocks B1, B2, . . . , BN each having a length equal to P where N is an integer equal to or greater than 2; (c) generating or recording first sequence permutation data in which elements of a Galois field of a characteristic P are arranged in an order of values of exponent parts of a power notation of the elements; (d) generating or recording (Nxe2x88x921) integers p1, p2, . . . , pNxe2x88x921 which are mutually prime with respect to (Pxe2x88x921); (e) generating or recording second through Nth sequence permutation data by repeating, ith times (i=1xe2x88x92(Nxe2x88x921)), a process for generating ith sequence permutation data by cyclically reading data in the first sequence permutation data at intervals of p1; (f) permuting data in the blocks B1-BN in accordance with the first through Nth sequence permutation data; and (g) reading permuted data from the blocks B1-BN in a given order.
The above-mentioned objects of the present invention are also achieved by an interleaving method comprising the steps of: (a) generating or recording a prime number P; (b) dividing an input sequence into N blocks B1, B2, . . . , BN each having a length equal to P where N is an integer equal to or greater than 2; (c) generating or recording zeroth sequence permutation data in which elements of a Galois field of a characteristic P are arranged in an order of values of exponent parts of a power notation of the elements; (d) generating or recording N integers p1, p2, . . . , pN which are mutually prime with respect to a primitive root used in the power notation; (e) generating or recording first through Nth sequence permutation data by repeating, ith times (i=1xe2x88x92N), a process for generating ith sequence permutation data which is a sequence of values of exponent parts in power notation of elements obtained by adding qi to data of the zeroth sequence permutation data; (f) permuting data in the blocks B1-BN in accordance with the first through Nth sequence permutation data; and (g) reading permuted data from the blocks B1-BN in a given order.
In the above step (b), each of the blocks may have a length equal to (Pxe2x88x921) or (P+1).
The above-mentioned objects of the present invention are also achieved by an interleaving apparatus which implements the above method.
The above-mentioned objects of the present invention are also achieved by a turbo encoding method comprising, as an interleaving method employed in a turbo encoder, the interleaving method as described above.
The above-mentioned objects of the present invention are also achieved by a turbo encoder comprising: a plurality of encoders; and the interleaving apparatus as described above.